#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

#include "buddy.h"
#include "mmzone.h"
#include "mmpage.h"
#include "list.h"
#include "buddy.h"
#include "math.h"
#include "utils.h"
#include "slab.h"

//这个程序将使用buddy来管理物理内存 0x00000000-0x40000000的内存的值
//暴露出去的接口是page_alloc和page_free 这两个接口将会申请PAGE_SIZE的页面大小
struct buddy buddy;
struct zone mem_zone;
struct page* pages;

//根据order获取伙伴系统的头
static inline struct page* get_align_down_buddy_page(struct page* p,int order){
    int pfn = p - pages;        //获取当前页框号
    int pfn_align_down = ALIGN_DOWN(pfn,POWER2(order+1));
    return pages + pfn_align_down;
}

//根据页获取其伙伴页
static inline struct page* get_buddy_page(struct zone*z ,struct page*p ,int order){
    if(order < 0 || order >= CONFIG_BUDDY_MAX_ORDER){
        return 0;
    }
    int pfn = p - pages;
    //利用异或来求伙伴页
    return pages + (pfn ^ POWER2(order));
}


static inline void memlist_out(struct zone* z,struct page* p){
    
    int order = p->private;
    // printf("memlist_out p = %x order = %x \n",p, order);
    //将指针从链表中删去
    struct list_head* entry = &p->list;
    list_del(entry);
    //将指针置成空
    INIT_LIST_HEAD(entry);
    //将相应的管理nr_free减少
    z->free_ares[order].nf_free--;
}

static inline int get_pfn(struct page* p){
    return p - pages;
}


static inline void memlist_in(struct zone*z ,struct page* p){
    
    int order = p->private;
    // printf("memlist_in p = %x order = %x \n",p, order);
    struct list_head *new = &p->list;
    struct list_head *entry = &z->free_ares[order].free_list;
    list_add_tail(new,entry);
    z->free_ares[order].nf_free++;
}

void zone_init(){
    struct zone* z = &mem_zone;
    z->zone_start_pfn = CONFIG_ADDR_START >> CONFIG_PAGE_SHIFT;
    z->managed_pages = (CONFIG_ADDR_END - CONFIG_ADDR_START) >> CONFIG_PAGE_SHIFT;
    z->free_pages = z->managed_pages;

    //非侵入式的内存管理，使用malloc申请空间
    pages = z->zone_mem_map = (struct page *)malloc(sizeof(struct page) * z->managed_pages);
    memset(pages,0,sizeof(struct page) * z->managed_pages / sizeof(unsigned char));
    for (size_t i = 0; i < CONFIG_BUDDY_MAX_ORDER; i++){
        INIT_LIST_HEAD(&z->free_ares[i].free_list);
    }
    
    // printf("zone start_pfn = %lu managed_pages = %lu \n",
    //             z->zone_start_pfn,z->managed_pages);

    // for (size_t i = 0; i < z->managed_pages; i++)
    // {
    //     printf("pages[%lu] = {private = %lu map = %lu} addr = %x \n"
    //         ,i,pages[i].private,pages[i]._mapcount,&pages[i]);
    // }
    
}


void buddy_alloctor_init(){
    struct zone* z = &mem_zone;
    printf("--------------alloctor_init start--------------\n");
    //初始化相应的数据结构
    //创建bitmap管理所有的页，一个bit代表一个页
    //为所有的Page创建一个数据结构
    buddy.manage_zone = &mem_zone;
    int pages_left = mem_zone.managed_pages;
    unsigned long start_pfn = z->zone_start_pfn;

    for (int i = CONFIG_BUDDY_MAX_ORDER - 1 ; i >=0; i--){
        if(pages_left <= 0){
            z->free_ares[i].nf_free = 0;
            continue;
        }
        
        //计算出有多少个block
        int do_pages = pages_left - (pages_left % (1<<i));
        int blocks = (do_pages / (1<<i));
        for (int j = 0; j < blocks; j++){
            //将每个block的首个pageframe 挂载链表上
            //计算是第几个pageframe 
            int pfn = start_pfn + (1<<i) * j;
            struct page* cur  =  pages + pfn;
            cur->private = i;
            list_add_tail(&cur->list,&z->free_ares[i].free_list);
        }
        z->free_ares[i].nf_free = blocks;
        pages_left -= do_pages;
    }
   printf("--------------alloctor_init end--------------\n");
}


void show_buddy_all_free_ares(){
    struct zone* z = &mem_zone;
    for (int i = 0; i < CONFIG_BUDDY_MAX_ORDER; i++){
        printf("i = %d  free_block = %lu \n",i,z->free_ares[i].nf_free);
    }
    
}

struct page* buddy_alloc_pages(int order){
    struct zone* z = &mem_zone;
    //在order的队列中拿一个节点
    if(order < 0 || order >= CONFIG_BUDDY_MAX_ORDER){
        printf("error order... \n");
        return 0;
    }

    if(z->free_ares[order].nf_free >0){
        //有相应的block则直接返回相应的pageframe
        struct list_head *entry = z->free_ares[order].free_list.next;
        struct page* tmp = list_entry(entry,struct page,list);

        memlist_out(z,tmp);
        return tmp;
    }else{
        //没有相应的block则申请大一倍的，再将其一半放回到order-1的链表中
        struct page* tmp = buddy_alloc_pages(order + 1);
        if(tmp == 0){
            printf("has no enough page frame to alloc. \n");
            return 0;
        }
        tmp->private = order;
        
        //将后面的一部分放回free_areas中
        struct page* reserved = tmp + POWER2(order);
        reserved->private = order;  
        memlist_in(z,reserved);
        //前半部分作为结果返回
        return tmp;
    }
}



void buddy_free_pages(struct page * p){
    struct zone* z = &mem_zone;
    //将p放回free_areas的链表中
    int order = p->private;

    struct list_head* entry = &z->free_ares[order].free_list;
    if(order == CONFIG_BUDDY_MAX_ORDER - 1){
        // printf("top order just add tail .\n");
        //如果是order是最高级的 直接放回不考虑merge
        memlist_in(z,p);
        // list_add_tail(&p->list,entry);
        // z->free_ares[order].nf_free++;
        return;
    }

    //根据其order找到其伙伴，判断其伙伴是否是free状态
    struct page* buddy_page =  get_buddy_page(z,p,order);
    //允许merge的情况：伙伴的block是free状态的 && 伙伴的block和当前block有相同的order
    if(buddy_page != 0 && !list_empty(&buddy_page->list) && buddy_page->private == order){
        // printf("merge available order = %d \n",order);
        //如果其伙伴都是free状态则merge到order+1的free_areas中
        memlist_out(z,buddy_page);  

        //放到order++的free_areas中
        struct page* tmp = get_align_down_buddy_page(buddy_page,order);
        tmp->private++;
        buddy_free_pages(tmp);
    }else{
        // printf("merge invaild just add tail order = %d \n",order);
        //如果不是则将其放回链表中
        memlist_in(z,p);
        // list_add_tail(&p->list,entry);
        // z->free_ares[order].nf_free++;
    }
}

void buddy_alloctor_free(){
    //释放申请的数据
    free(pages);
}

#define BUDDY_TEST_MAX  10000

void buddy_test(){
    //在buddy上申请物理地址， 然后释放观察free_ares的状态
    int pages_left = mem_zone.managed_pages;
    srand(time(0));
    struct page* alloc_save[BUDDY_TEST_MAX];
    int index = 0;
    while (1){
        //随机申请物理页
        int tmp_rand =  rand()%CONFIG_BUDDY_MAX_ORDER;  //获取rand() 最靠左的1 并且返回
        if(pages_left >= POWER2(tmp_rand)){
            // printf("test pages_left = %d ==> buddy_alloc_pages(%d) \n",pages_left,tmp_rand);
            struct page *tmp_page = buddy_alloc_pages(tmp_rand);
            if(tmp_page != 0){
                alloc_save[index] = tmp_page;
                // printf("alloc_save[%d] ==> pfn = %d order = %d \n",
                //         index,get_pfn(alloc_save[index]),alloc_save[index]->private);
                index++;
                pages_left -= POWER2(tmp_rand);
            }else{
                printf("buddy_alloc_pages error. \n");
            }
        }
        if(index == BUDDY_TEST_MAX-1 || pages_left <= 0){
            break;
        }
    }

    printf("alloc end ==>  alloc_step = %d  \n",index);
    int free_index = 0;
    //释放所有申请的物理页
    while (free_index < index)
    {
        struct page* free_tmp = (struct page* )alloc_save[free_index];
        // printf("start free index = %d  pfn = %x order = %d \n",
        //         free_index,get_pfn(free_tmp),free_tmp->private);
        free_index++;
        buddy_free_pages(free_tmp);
    }
    printf("after free pages ==>free_areas status: \n");
    show_buddy_all_free_ares(&mem_zone);
}